class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode node1(0);
        ListNode node2(0);

        ListNode* cur1 = &node1;
        ListNode* cur2 = &node2;

        ListNode* cur = head;
        while(cur)
        {
            if(cur->val < x)
            {
                cur1->next = cur;
                cur1 = cur1->next;
            }
            else
            {
                cur2->next = cur;
                cur2 = cur2->next;
            }

            cur = cur->next;
        }

        cur1->next = node2.next;
        cur2->next = nullptr;


        return node1.next;
    }
};
